home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / index-rtree / rtstrat.c < prev   
Encoding:
C/C++ Source or Header  |  1992-08-27  |  7.8 KB  |  230 lines
  1. /*
  2.  *  rtstrat.c -- strategy map data for rtrees.
  3.  */
  4. #include "tmp/c.h"
  5.  
  6. #include "utils/rel.h"
  7.  
  8. #include "storage/bufmgr.h"
  9. #include "storage/bufpage.h"
  10. #include "storage/page.h"
  11.  
  12. #include "access/isop.h"
  13. #include "access/istrat.h"
  14. #include "access/rtree.h"
  15.  
  16. RcsId("$Header: /private/postgres/src/access/index-rtree/RCS/rtstrat.c,v 1.3 1991/02/27 19:32:47 mao Exp $");
  17.  
  18. /*
  19.  *  Note:  negate, commute, and negatecommute all assume that operators are
  20.  *       ordered as follows in the strategy map:
  21.  *
  22.  *    left, left-or-overlap, overlap, right-or-overlap, right, same,
  23.  *    contains, contained-by
  24.  *
  25.  *  The negate, commute, and negatecommute arrays are used by the planner
  26.  *  to plan indexed scans over data that appears in the qualificiation in
  27.  *  a boolean negation, or whose operands appear in the wrong order.  For
  28.  *  example, if the operator "<%" means "contains", and the user says
  29.  *
  30.  *    where not rel.box <% "(10,10,20,20)"::box
  31.  *
  32.  *  the planner can plan an index scan by noting that rtree indices have
  33.  *  an operator in their operator class for negating <%.
  34.  *
  35.  *  Similarly, if the user says something like
  36.  *
  37.  *    where "(10,10,20,20)"::box <% rel.box
  38.  *
  39.  *  the planner can see that the rtree index on rel.box has an operator in
  40.  *  its opclass for commuting <%, and plan the scan using that operator.
  41.  *  This added complexity in the access methods makes the planner a lot easier
  42.  *  to write.
  43.  */
  44.  
  45. /* if a op b, what operator tells us if (not a op b)? */
  46. static StrategyNumber    RTNegate[RTNStrategies] = {
  47.     InvalidStrategy,
  48.     InvalidStrategy,
  49.     InvalidStrategy,
  50.     InvalidStrategy,
  51.     InvalidStrategy,
  52.     InvalidStrategy,
  53.     InvalidStrategy,
  54.     InvalidStrategy
  55. };
  56.  
  57. /* if a op_1 b, what is the operator op_2 such that b op_2 a? */
  58. static StrategyNumber    RTCommute[RTNStrategies] = {
  59.     InvalidStrategy,
  60.     InvalidStrategy,
  61.     InvalidStrategy,
  62.     InvalidStrategy,
  63.     InvalidStrategy,
  64.     InvalidStrategy,
  65.     InvalidStrategy,
  66.     InvalidStrategy
  67. };
  68.  
  69. /* if a op_1 b, what is the operator op_2 such that (b !op_2 a)? */
  70. static StrategyNumber    RTNegateCommute[RTNStrategies] = {
  71.     InvalidStrategy,
  72.     InvalidStrategy,
  73.     InvalidStrategy,
  74.     InvalidStrategy,
  75.     InvalidStrategy,
  76.     InvalidStrategy,
  77.     InvalidStrategy,
  78.     InvalidStrategy
  79. };
  80.  
  81. /*
  82.  *  Now do the TermData arrays.  These exist in case the user doesn't give
  83.  *  us a full set of operators for a particular operator class.  The idea
  84.  *  is that by making multiple comparisons using any one of the supplied
  85.  *  operators, we can decide whether two n-dimensional polygons are equal.
  86.  *  For example, if a contains b and b contains a, we may conclude that
  87.  *  a and b are equal.
  88.  *
  89.  *  The presence of the TermData arrays in all this is a historical accident.
  90.  *  Early in the development of the POSTGRES access methods, it was believed
  91.  *  that writing functions was harder than writing arrays.  This is wrong;
  92.  *  TermData is hard to understand and hard to get right.  In general, when
  93.  *  someone populates a new operator class, the populate it completely.  If
  94.  *  Mike Hirohama had forced Cimarron Taylor to populate the strategy map
  95.  *  for btree int2_ops completely in 1988, you wouldn't have to deal with
  96.  *  all this now.  Too bad for you.
  97.  *
  98.  *  Since you can't necessarily do this in all cases (for example, you can't
  99.  *  do it given only "intersects" or "disjoint"), TermData arrays for some
  100.  *  operators don't appear below.
  101.  *
  102.  *  Note that if you DO supply all the operators required in a given opclass
  103.  *  by inserting them into the pg_opclass system catalog, you can get away
  104.  *  without doing all this TermData stuff.  Since the rtree code is intended
  105.  *  to be a reference for access method implementors, I'm doing TermData
  106.  *  correctly here.
  107.  *
  108.  *  Note on style:  these are all actually of type StrategyTermData, but
  109.  *  since those have variable-length data at the end of the struct we can't
  110.  *  properly initialize them if we declare them to be what they are.
  111.  */
  112.  
  113. /* if you only have "contained-by", how do you determine equality? */
  114. static uint16 RTContainedByTermData[] = {
  115.     2,                    /* make two comparisons */
  116.     RTContainedByStrategyNumber,        /* use "a contained-by b" */
  117.     0x0,                    /* without any magic */
  118.     RTContainedByStrategyNumber,        /* then use contained-by, */
  119.     CommuteArguments            /* swapping a and b */
  120. };
  121.  
  122. /* if you only have "contains", how do you determine equality? */
  123. static uint16 RTContainsTermData[] = {
  124.     2,                    /* make two comparisons */
  125.     RTContainsStrategyNumber,        /* use "a contains b" */
  126.     0x0,                    /* without any magic */
  127.     RTContainsStrategyNumber,        /* then use contains again, */
  128.     CommuteArguments            /* swapping a and b */
  129. };
  130.  
  131. /* now put all that together in one place for the planner */
  132. static StrategyTerm RTEqualExpressionData[] = {
  133.     (StrategyTerm) RTContainedByTermData,
  134.     (StrategyTerm) RTContainsTermData,
  135.     NULL
  136. };
  137.  
  138. /*
  139.  *  If you were sufficiently attentive to detail, you would go through
  140.  *  the ExpressionData pain above for every one of the seven strategies
  141.  *  we defined.  I am not.  Now we declare the StrategyEvaluationData
  142.  *  structure that gets shipped around to help the planner and the access
  143.  *  method decide what sort of scan it should do, based on (a) what the
  144.  *  user asked for, (b) what operators are defined for a particular opclass,
  145.  *  and (c) the reams of information we supplied above.
  146.  *
  147.  *  The idea of all of this initialized data is to make life easier on the
  148.  *  user when he defines a new operator class to use this access method.
  149.  *  By filling in all the data, we let him get away with leaving holes in his
  150.  *  operator class, and still let him use the index.  The added complexity
  151.  *  in the access methods just isn't worth the trouble, though.
  152.  */
  153.  
  154. static StrategyEvaluationData RTEvaluationData = {
  155.     RTNStrategies,                /* # of strategies */
  156.     (StrategyTransformMap) RTNegate,    /* how to do (not qual) */
  157.     (StrategyTransformMap) RTCommute,    /* how to swap operands */
  158.     (StrategyTransformMap) RTNegateCommute,    /* how to do both */
  159.     NULL,                    /* express left */
  160.     NULL,                    /* express overleft */
  161.     NULL,                    /* express over */
  162.     NULL,                    /* express overright */
  163.     NULL,                    /* express right */
  164.     (StrategyExpression) RTEqualExpressionData,    /* express same */
  165.     NULL,                    /* express contains */
  166.     NULL                    /* express contained-by */
  167. };
  168.  
  169. /*
  170.  *  Okay, now something peculiar to rtrees that doesn't apply to most other
  171.  *  indexing structures:  When we're searching a tree for a given value, we
  172.  *  can't do the same sorts of comparisons on internal node entries as we
  173.  *  do at leaves.  The reason is that if we're looking for (say) all boxes
  174.  *  that are the same as (0,0,10,10), then we need to find all leaf pages
  175.  *  that overlap that region.  So internally we search for overlap, and at
  176.  *  the leaf we search for equality.
  177.  *
  178.  *  This array maps leaf search operators to the internal search operators.
  179.  *  We assume the normal ordering on operators.
  180.  */
  181. static StrategyNumber RTOperMap[RTNStrategies] = {
  182.     RTOverLeftStrategyNumber,
  183.     RTOverLeftStrategyNumber,
  184.     RTOverlapStrategyNumber,
  185.     RTOverRightStrategyNumber,
  186.     RTOverRightStrategyNumber,
  187.     RTOverlapStrategyNumber,
  188.     RTContainsStrategyNumber,
  189.     RTContainedByStrategyNumber
  190. };
  191.  
  192. StrategyNumber
  193. RelationGetRTStrategy(r, attnum, proc)
  194.     Relation r;
  195.     AttributeNumber attnum;
  196.     RegProcedure proc;
  197. {
  198.     return (RelationGetStrategy(r, attnum, &RTEvaluationData, proc));
  199. }
  200.  
  201. bool
  202. RelationInvokeRTStrategy(r, attnum, s, left, right)
  203.     Relation r;
  204.     AttributeNumber attnum;
  205.     StrategyNumber s;
  206.     Datum left;
  207.     Datum right;
  208. {
  209.     return (RelationInvokeStrategy(r, &RTEvaluationData, attnum, s,
  210.                        left, right));
  211. }
  212.  
  213. RegProcedure
  214. RTMapOperator(r, attnum, proc)
  215.     Relation r;
  216.     AttributeNumber attnum;
  217.     RegProcedure proc;
  218. {
  219.     StrategyNumber procstrat;
  220.     RegProcedure newproc;
  221.     StrategyMap strategyMap;
  222.  
  223.     procstrat = RelationGetRTStrategy(r, attnum, proc);
  224.     strategyMap = IndexStrategyGetStrategyMap(RelationGetIndexStrategy(r),
  225.                           RTNStrategies,
  226.                           attnum);
  227.  
  228.     return (strategyMap->entry[RTOperMap[procstrat - 1] - 1].procedure);
  229. }
  230.